package JZ;

public class jz12dfs {
    public static void main(String[] args) {
        boolean re = hasPath(new char[][]{{'a','b','c','e'},{'s','f','c','s'},{'a','d','e','e'}}, "abcced");
        System.out.println(re);
    }
    public static boolean hasPath (char[][] matrix, String word) {
        int[][] used = new int[matrix.length][matrix[0].length];
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if(matrix[i][j] == word.charAt(0))
                    if(dfs2(matrix, word, used, i, j, 0))
                        return true;
            }
        }
       return false;
    }
    public static boolean dfs2(char[][] matrix, String word, int[][] used, int i, int j, int index) {
        if (i >= matrix.length || i < 0 || j < 0 || j >= matrix[0].length || used[i][j] == 1)
            return false;
        if (index == word.length() - 1 && word.charAt(index) == matrix[i][j] && used[i][j] == 0)
            return true;
        if (word.charAt(index) == matrix[i][j]) {
            used[i][j] = 1;
            if (dfs2(matrix, word, used, i - 1, j, index + 1)
                    || dfs2(matrix, word, used, i + 1, j, index + 1)
                    || dfs2(matrix, word, used, i, j - 1, index + 1)
                    || dfs2(matrix, word, used, i, j + 1, index + 1))
                return true;
        }
        used[i][j] = 0;
        return false;

    }
}
